package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

/**
 * <a href="https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/">O(1) 时间插入、删除和获取随机元素 - 允许重复(Insert Delete GetRandom O(1) - Duplicates allowed)</a>
 * <p>{@code RandomizedCollection} 是一种包含数字集合(可能是重复的)的数据结构。它应该支持插入和删除特定元素，以及删除随机元素。实现 {@code RandomizedCollection} 类:
 * <ul>
 *     <li>{@code RandomizedCollection()}初始化空的 {@code RandomizedCollection} 对象。</li>
 *     <li>{@code bool insert(int val)} 将一个 {@code val} 项插入到集合中，即使该项已经存在。如果该项不存在，则返回 {@code true} ，否则返回 {@code false} 。</li>
 *     <li>{@code bool remove(int val)} 如果存在，从集合中移除一个 {@code val} 项。如果该项存在，则返回 {@code true} ，否则返回 {@code false} 。注意，如果 {@code val} 在集合中出现多次，我们只删除其中一个。</li>
 *     <li>{@code int getRandom()} 从当前的多个元素集合中返回一个随机元素。每个元素被返回的概率与集合中包含的相同值的数量<b>线性相关</b>。</li>
 * </ul>
 * </p>
 * <p>您必须实现类的函数，使每个函数的 平均 时间复杂度为 O(1) 。</p>
 * <p>注意：生成测试用例时，只有在 RandomizedCollection 中 至少有一项 时，才会调用 getRandom 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入
 *          ["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
 *          [[], [1], [1], [2], [], [1], []]
 *      输出
 *          [null, true, false, true, 2, true, 1]
 *      解释
 *          RandomizedCollection collection = new RandomizedCollection();// 初始化一个空的集合。
 *          collection.insert(1);   // 返回 true，因为集合不包含 1。
 *                                  // 将 1 插入到集合中。
 *          collection.insert(1);   // 返回 false，因为集合包含 1。
 *                                  // 将另一个 1 插入到集合中。集合现在包含 [1,1]。
 *          collection.insert(2);   // 返回 true，因为集合不包含 2。
 *                                  // 将 2 插入到集合中。集合现在包含 [1,1,2]。
 *          collection.getRandom(); // getRandom 应当:
 *                                  // 有 2/3 的概率返回 1,
 *                                  // 1/3 的概率返回 2。
 *          collection.remove(1);   // 返回 true，因为集合包含 1。
 *                                  // 从集合中移除 1。集合现在包含 [1,2]。
 *          collection.getRandom(); // getRandom 应该返回 1 或 2，两者的可能性相同。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>-10^32 <= val <= 10^32</li>
 *      <li>insert, remove 和 getRandom 最多 总共 被调用 2 * 10^5 次</li>
 *      <li>当调用 getRandom 时，数据结构中 至少有一个 元素</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/12/9 14:38
 */
public class LC0381InsertDeleteGetRandom_H {
    static class RandomizedCollection {
        /**
         * 数字 与 在容器中所有索引 的映射关系
         */
        private final Map<Integer, Set<Integer>> idxMap = new HashMap<>();
        /**
         * 用于存放所有数字的容器
         */
        private final List<Integer> container = new ArrayList<>();

        private final Random RANDOM = new Random();

        public RandomizedCollection() {

        }

        public boolean insert(int val) {
            // 添加到容器对应的索引中
            Set<Integer> idxSet = idxMap.computeIfAbsent(val, k -> new HashSet<>());
            idxSet.add(container.size());
            // 添加到容器中
            container.add(val);
            // 第一次插入，元素个数为1，返回true；否则返回false。
            return idxSet.size() == 1;
        }

        public boolean remove(int val) {
            Set<Integer> targetValSet = idxMap.get(val);
            if (targetValSet == null) {
                return false;
            }
            // 使用迭代器获取一个set集合中的元素
            int targetValIndex = targetValSet.iterator().next();
            // 不能直接调用 List.removeIndex()移除元素。这种方式后续所有元素的索引都会-1，影响的节点太多
            // 思路是，将目标节点与最后一个节点交换索引，只删除交换的最后一个节点
            // 1.找到最后一个元素
            Integer lastElementVal = container.get(container.size() - 1);
            // 2.将目标元素与最后一个元素交换
            container.set(targetValIndex, lastElementVal);
            // 3.将目标元素从所在的索引集中移除
            targetValSet.remove(targetValIndex);
            // 4.替换最后一个元素的索引，先增后删：用于解决：删除的恰好是是最后一个元素
            Set<Integer> lastElementValIdxSet = idxMap.get(lastElementVal);
            lastElementValIdxSet.add(targetValIndex);
            lastElementValIdxSet.remove(container.size() - 1);
            // 5.删除目标元素
            container.remove(container.size() - 1);
            // 如果删除目标元素索引后，不在含有其他索引，则从map中移除
            if (targetValSet.isEmpty()) {
                idxMap.remove(val);
            }
            return true;
        }

        public int getRandom() {
            return container.get(RANDOM.nextInt(container.size()));
        }
    }

    public static void main(String[] args) {
        //System.out.println("======");
        //RandomizedCollection randomizedCollection1 = new RandomizedCollection();
        //System.out.println(randomizedCollection1.insert(1));    // true
        //System.out.println(randomizedCollection1.insert(1));    // false
        //System.out.println(randomizedCollection1.insert(2));    // true
        //System.out.println(randomizedCollection1.getRandom());      // 1、2
        //System.out.println(randomizedCollection1.remove(1));    // true
        //System.out.println(randomizedCollection1.getRandom());      // 1、2
        //System.out.println("======");
        //RandomizedCollection randomizedCollection2 = new RandomizedCollection();
        //System.out.println(randomizedCollection2.insert(0));    // true
        //System.out.println(randomizedCollection2.insert(1));    // true
        //System.out.println(randomizedCollection2.remove(0));    // true
        //System.out.println(randomizedCollection2.insert(2));    // true
        //System.out.println(randomizedCollection2.remove(1));    // true
        //System.out.println(randomizedCollection2.getRandom());      // 2
        //System.out.println("======");
        //RandomizedCollection randomizedCollection3 = new RandomizedCollection();
        //System.out.println(randomizedCollection3.insert(4));    // true
        //System.out.println(randomizedCollection3.insert(3));    // true
        //System.out.println(randomizedCollection3.insert(4));    // false
        //System.out.println(randomizedCollection3.insert(2));    // true
        //System.out.println(randomizedCollection3.insert(4));    // false
        //System.out.println(randomizedCollection3.remove(4));    // true
        //System.out.println(randomizedCollection3.remove(3));    // true
        //System.out.println(randomizedCollection3.remove(4));    // true
        //System.out.println(randomizedCollection3.remove(4));    // true
        //System.out.println("======");
        RandomizedCollection randomizedCollection4 = new RandomizedCollection();
        System.out.println(randomizedCollection4.insert(0));    // true
        System.out.println(randomizedCollection4.remove(0));    // true
        System.out.println(randomizedCollection4.insert(-1));   // true
        System.out.println(randomizedCollection4.remove(0));    // false
        System.out.println(randomizedCollection4.getRandom());      // -1
        System.out.println(randomizedCollection4.getRandom());      // -1
        System.out.println(randomizedCollection4.getRandom());      // -1
        System.out.println(randomizedCollection4.getRandom());      // -1
        System.out.println(randomizedCollection4.getRandom());      // -1
        System.out.println(randomizedCollection4.getRandom());      // -1
        System.out.println(randomizedCollection4.getRandom());      // -1
        System.out.println(randomizedCollection4.getRandom());      // -1
        System.out.println(randomizedCollection4.getRandom());      // -1
        System.out.println(randomizedCollection4.getRandom());      // -1
        System.out.println("======");
    }
}
